1. Field of the Invention
The invention relates in general to a method for motion estimation in video coding, and more particularly to a block-matching motion estimation method for motion compensated video coding.
2. Description of the Related Art
In conventional motion compensated video coding, when a current frame is to be processed, it involves computation of a motion vector by using a previous frame or a reference frame and then the current frame is processed. The motion vector is produced by a motion estimation technique. Among motion estimation techniques, a block matching motion estimation technique is frequently used, wherein the smallest estimation unit is a block of a frame.
Referring to FIG. 1, it illustrates a conventional motion compensated video coding. In FIG. 1, block 104 of frame 102 is coded as follows. First, it needs to determine a block, such as block 108, which matches block 104 best and makes less difference to block 104, by using a block matching motion estimation technique with a previous frame 106. Then, a motion vector is obtained by computing the difference in coordinates between the pixels of block 104 in frame 102 and the pixels of block 108 in frame 106. Next, this motion vector and the difference in image information between block 104 and block 108 are coded. In this way, for transmitting the image data of frame 102, the data encoded by the technique above are actually transmitted and significantly reduced in quantity as compared with other technique in which block 104 is required to be coded entirely.
A conventional block matching motion estimation technique is the fill search technique. By the full search technique, a complete test is performed, resulting in the best-matching block for a current frame. Referring to FIG. 2, it illustrates the conventional full search motion estimation technique. When block 104 is to be coded, the method for searching the best-matching block in the previous frame 106 by using the full search technique is as follows.
First, determine search region 202 corresponding to frame 106, where the size of search region 202 can be determined according to the characteristics of the image data of frames 102 and 106. In search region 202, there are M by M checking points, each of which corresponds to a block of frame 106. For example, referring to FIG. 2B, it illustrates the relationship between checking points and their respective blocks. In FIG. 2B, checking points C, C1, and C2 correspond to blocks 204, 206, and 208 of the previous frame 106 respectively. If checking point C moves right and upward by one pixel, it becomes checking point C1. In this way, when the region indicated by block 204 is shifted right and upward by one pixel, it results in the region indicated by block 206.
Secondly, computation of the differences in image information of all pixels between the blocks corresponding to all checking points and block 104 of the current frame 102 is performed.
Next, a block match error is determined by summing the absolute values of the differences in image information for one block.
Then, it is to determine the block corresponding to the minimum block match error by using the block match errors determined, wherein the block determined to have the minimum block match error is the best-matching block in the previous frame 106, such as block 108 in this example.
After that, a motion vector for block 104 is obtained by the checking point that corresponds to the best-matching block in the previous frame 106, block 108.
In the full search motion estimation technique, checking points are consecutively determined in a search region so that the arrangement of the blocks corresponding to the checking points is in consecutive order and two consecutive blocks overlap. In this way, when performing a full search for a best-matching block, many image data may be reused. Referring to FIG. 2C, it illustrates image data reuse when performing a full search. In FIG. 2C, three consecutive checking points in a row correspond to blocks 210, 212, and 214. During performing computation on each pixel of block 212, it only needs to load the image data of block 212 which correspond to the portion that does not overlap block 210. Similarly, during performing computation on each pixel of block 214, it is only required loading the image data of block 214 which correspond to the portion that does not overlap block 212. Consequently, a small amount of data is loaded in computation for each block. By hardware design, the function of data reuse can be achieved. In this way, most media processors for performing video coding generally support speed-up hardware to improve the performance when performing full search motion estimation.
However, the full search motion estimation technique involves a huge amount of complex computation. It consumes time to perform and thus the performance is low. Therefore, for a better performance, many block matching motion estimation techniques have been developed. Referring to FIG. 3, it illustrates one block matching motion estimation technique called three step search (TSS) technique. First, nine checking points are taken, wherein eight of them form an 8xc3x978 pixels square, such as square 302, with the remaining checking point, such as checking point P, as the square""s center point. Then, the block match errors for the blocks corresponding to all checking point of square 302 are calculated, and from the checking points taken from square 302, the checking point corresponding to the minimum block match error calculated can be determined, such as checking point P1 in square 302. Next, from a 4-by-4-pixel square, such as square 304, with checking point P1 as its center point, eight checking points are taken and the checking point corresponding to the minimum block match error can be determined, such as checking point P2. Finally, from the eight checking points adjacent to checking point P2, the checking point that corresponds to the block with the minimum block match error is determined, such as checking point P3. In this way, a motion vector can be determined by using checking point P3.
In the three step search technique, the number of checking points employed in the process of determination of a motion vector is less than the full search technique so that the amount of computation in the three step search technique does as well. However, performance of the three step search technique is not completely accepted. By the three step search technique, the point check for obtaining the motion vector is determined through only three steps, it is probably that the checking point corresponding to the best-matching block cannot be found. Besides, as can be seen from the example above, the distribution of the checking points is non-uniform. Thus, it cannot be benefited from the hardware""s speed-up, as the full search technique does, to speed up the processing rate.
In addition, another block matching motion estimation technique, called diamond search technique, has been widely used. Referring to FIG. 4, it illustrates the conventional diamond search technique. First, nine checking points are taken, wherein eight of them form a rhombus, such as rhombus 402, with the remaining checking point such as D, as the rhombus""s center point and the diagonals of the rhombus are of four pixels length. Second, the block match errors corresponding to all checking points taken from rhombus 402 are calculated and checking point D1 is determined as the checking point corresponding to the minimum block match error. Since checking point D1 is not the center point D1 rhombus 402, eight checking points are taken from rhombus 404 with checking point D1 as the center point and with diagonals of four pixels length and, from the eight checking points from rhombus 404, checking point D2 is determined as the checking point corresponding to the minimum block match error. Since checking point D2 is not the center point of rhombus 404, eight checking points is taken from rhombus 406 with checking point D2 as the center point and with diagonals of four pixels length, and the checking point corresponding to the minimum block match error is to be determined from the eight checking points from rhombus 406. If it is determined that checking point D2, the center point of rhombus 406, is the checking point corresponding to the minimum block match error for rhombus 406, four checking points are taken from the rhombus 408 with checking point D2 as the center point and with diagonals of two pixels length and, from the four checking points from rhombus 408, checking point D3 is determined as the checking point corresponding to the minimum block match error. In this way, a motion vector can be determined by using checking point D3.
By the diamond search technique, since the block match error corresponding to the checking point, such as checking point D3 in the example above, is the local minimum block match error. Thus, the performance is acceptable. In addition, the diamond search technique provides low complexity. However, in this technique, since the sequence of access to data is irregular, so that data reuse cannot be achieved and its performance cannot be benefited from the speed-up function supported by the hardware. Besides, because of the irregular sequence of access to data, a lot of time is consumed in selection, determination, and calculation of data""s address, and the time taken in these control actions significantly affects the processing rate of the diamond search technique.
It is therefore an object of the invention to provide a method for video coding motion estimation. By the invention, it is to achieve high quality, low complexity, capability of data reuse and capability of utilizing speed-up hardware supported by most media processors to increase the processing rate of video coding.
The invention achieves the above-identified objects by providing a method for motion estimation for use in video coding and when a first block in a current frame is coded, the method is used for searching for a second block in a previous frame matching the first block in the current frame. The second block is used for determining a motion vector, in a predetermined search region, for the first block. In the predetermined search region, there are a number of rows and the number of rows including an (Nxe2x88x922)-th row, an (Nxe2x88x921)-th row, an N-th row, an (N+1)-th row, and an (N+2)-th row, each of the rows having a number of points, wherein a prediction point is on the N-th row. The method includes the following steps. (a) All points of the (Nxe2x88x922)-th row, the N-th row, and the (N+2)th row are chosen as checking points. (b) Block match errors for the checking points are calculated and a checking point which corresponds to a minimum block match error is defined as a candidate checking point. (c) A determination is made whether the candidate checking point is on the N-th row; if the candidate checking point is on the N-th row, the method proceeds to step (g); otherwise, the method proceeds to step (d). (d) It is determined that whether the candidate checking point is on the (N+2)-th row; if the candidate checking point is on the (N+2)-th row, the method proceeds to step (e); otherwise, the method proceeds to step (f). (e) N is incremented by two, all points of the (N+2)-th row are chosen as checking points, and step (b) is repeated. (f) N is decremented by two, all points of the (Nxe2x88x922)-th row are chosen as checking points, and step (b) is repeated. (g) All points of the (Nxe2x88x921)-th and the (N+1)-th rows are chosen as checking points, block match errors for the checking points are calculated, and a checking point corresponding to the minimum block match error is defined as the candidate checking point, wherein the candidate checking point corresponds to the second block and is used for determining the motion vector for the first block.